// 选择排序

#include <iostream>
#include <algorithm>

void selectionSort(int arr[], int n)
{
    int minIndex = 0;

    for (int i = 0; i < n - 1; ++i) // 遍历n-1趟(原因 : 最后一个元素随前面排序完成自动完成, 最后一个元素可以忽略排序)
    {
        minIndex = i;
        for (int j = i + 1; j < n; ++j) // 遍历i下标后的所有元素找最小的元素
        {
            if (arr[j] < arr[minIndex]) // 最小值索引
            {
                minIndex = j;
            }
        }

        if (minIndex != i)
        {
            std::swap(arr[minIndex], arr[i]);
        }
    }
}


void optimizeSelectionSort(int arr[], int n)
{
    int begin = 0;
    int end = n - 1;
    while(begin < end)
    {
        int maxIndex = begin;
        int minIndex = begin;
        for(int i = begin + 1; i <= end; ++i)
        {
            if(arr[i] > arr[maxIndex])
            {
                maxIndex = i;
            }
            if(arr[i] < arr[minIndex])
            {
                minIndex = i;
            }
        }
        std::swap(arr[begin], arr[minIndex]);
        if(maxIndex == begin)
        {
            maxIndex = minIndex;
        }
        if(maxIndex != end)
        {
            std::swap(arr[maxIndex], arr[end]);
        }
        ++begin;
        --end;
    }
}

